package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import common.printInorder
import java.util.*

/**

538. 把二叉搜索树转换为累加树
https://leetcode.cn/problems/convert-bst-to-greater-tree/description/

同 1038. 从二叉搜索树到更大和树
https://leetcode.cn/problems/binary-search-tree-to-greater-sum-tree/description/


给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

示例 1：
输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

示例 2：
输入：root = [0,null,1]
输出：[1,null,1]

示例 3：
输入：root = [1,0,2]
输出：[3,3,2]

示例 4：
输入：root = [3,2,4,1]
输出：[7,9,4,10]
 */
class leetcode_538 {
    @Test
    fun test_1() {
        val n0 = TreeNode(0)
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val n5 = TreeNode(5)
        val n6 = TreeNode(6)
        val n7 = TreeNode(7)
        val n8 = TreeNode(8)

        var path:ArrayList<Int> = ArrayList<Int>()
        val root = n4
        n4.left = n1
        n4.right = n6
        n1.left = n0
        n1.right = n2
        n2.right = n3
        n6.left = n5
        n6.right = n7
        n7.right = n8
        val result = convertBST(root)
        val actual = printInorder(result)
        val expect = arrayListOf(36, 36, 35, 33, 30, 26, 21, 15, 8)
        Assert.assertEquals(expect, actual)
    }

    @Test
    fun test_2() {
        val n0 = TreeNode(0)
        val n1 = TreeNode(1)
        n0.right = n1
        val root = n0

        val result = convertBST(root)
        val actual = printInorder(result)
        val expect = arrayListOf(1, 1)
        Assert.assertEquals(expect, actual)
    }


    @Test
    fun test_3() {
        val n0 = TreeNode(0)
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val root = n1
        root.left = n0
        root.right = n2

        val result = convertBST(root)
        val actual = printInorder(result)
        val expect = arrayListOf(3, 3, 2)
        Assert.assertEquals(expect, actual)
    }

    @Test
    fun test_4() {
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val root = n3
        root.left = n2
        root.right = n4
        n2.left = n1

        val result = convertBST(root)
        val actual = printInorder(result)
        val expect = arrayListOf(10, 9, 7, 4)
        Assert.assertEquals(expect, actual)
    }

    fun convertBST(root: TreeNode?): TreeNode? {
        // convertBST1(root)
        // return root
        return convertBST2(root)
    }


    var prev: Int = 0
    fun convertBST1(root: TreeNode?) {
        // 反中序遍历(右中左) - 迭代法 + prev 指针法
        // T - N
        // S - N

        // 终止条件
        if (null == root) {
            return
        }

        // 右
        convertBST1(root.right)

        // 中
        // val old : Int = root.`val`
        // val oldPrev:Int = prev
        root.`val` = root.`val` + prev
        prev = root.`val`
        // println("old prev ${oldPrev} -> new prev ${prev}, old $old -> new ${root.`val`}")


        // 左
        convertBST1(root.left)
    }

    fun convertBST2(root: TreeNode?): TreeNode? {
        // 反中序遍历(右中左) - 迭代法 + prev 指针法
        // T - N
        // S - N

        if (null == root) {
            return null
        }

        var prev: Int = 0
        val stack: LinkedList<Pair<TreeNode, Boolean>> = LinkedList<Pair<TreeNode, Boolean>>()
        stack.push(Pair<TreeNode, Boolean>(root, false))

        while (!stack.isEmpty()) {
            val pair: Pair<TreeNode, Boolean> = stack.pop()
            val node: TreeNode = pair.first
            val visited: Boolean = pair.second
            if (visited) {
                node.`val` = node.`val` + prev
                prev = node.`val`
                continue
            }
            // 左
            node.left?.let {
                stack.push(Pair<TreeNode, Boolean>(it, false))
            }
            // 中
            stack.push(Pair<TreeNode, Boolean>(node, true))
            // 右
            node.right?.let {
                stack.push(Pair<TreeNode, Boolean>(it, false))
            }
        }
        return root
    }
}